import copy

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        ret = []
        def palindrome(s):
            i = 0
            j = len(s)-1
            while i<j:
                if s[i]==s[j]:
                    i+=1
                    j-=1
                else: return False
            return True

        def find(seq, acc):
            if len(seq)==0:
                ret.append(copy.copy(acc))
                return
            for i in range(1, len(seq)+1):
                sub = seq[:i]
                if palindrome(sub):
                    acc.append(sub)
                    find(seq[i:], acc)
                    acc.pop()
        find(s, [])
        return ret

print(Solution().partition("aab"))